
//3439.重新安排会议得到最多空余时间I
class Solution {
    public:
        int maxFreeTime(int eventTime, int k, vector<int>& startTime, vector<int>& endTime) {
            //本题通过k次移动可以实现将k+1个会议进行整合，这也就实现了让k个会议左右两边的空余时间进行整合
            //所以本题就转化为了求k个会议两边空余时间的最大值
            //使用滑动窗口实现
            int n=startTime.size();
            int left=0,right=startTime[0];    //此处right要跳着走，不能使用right++，否则会超时
            int ret=0,tmp=k,intime=0,i=0;   //intime用来统计区间内会议的时长,i表示是第几个会议
            while(i<n)
            {
                //入窗口
                while(i<n&&tmp>=0)
                {
                    if(startTime[i]==right&&tmp==0) break;
                    if(startTime[i]==right) 
                    {
                        intime+=endTime[i]-startTime[i];  //统计区间内会议的时长
                        tmp--,i++;   //对left和right区间内的会议个数进行统计
                        if(i==n) return max(ret,eventTime-left-intime);
                        right=startTime[i];
                    }
                }
                //更新答案
                ret=max(ret,right-left-intime);
    
                //出窗口
                left = endTime[i - k];  //让left移动到区间内第一个会议结尾
                intime -= (endTime[i - k] - startTime[i - k]);   //此处减去区间内第一个会议时长
                tmp++ ; 
            }
            return ret;
        }
    };